/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class RemoveBoxes {
    public int removeBoxes(int[] boxes) {
    	int n=boxes.length;
    	int[][] dp=new int[n][n];
		System.out.println("i j "+"dp[i][j]"+" conti[j]");

    	for (int i = n-1; i >=0; i--) {
    		int[] conti=new int[n];//以j结尾的相同字符的 个数
			for (int j = i; j < n; j++) {
				dp[i][j]=i==j?1:dp[i][j-1]+1;
				conti[j]=1;
				for (int k = i; k < j; k++) {
					if(boxes[k]==boxes[j]){
						int tmp=dp[i][k]+dp[k+1][j-1]+2*conti[k]+1;
						if(dp[i][j]<tmp){
							dp[i][j]=tmp;
							conti[j]=conti[k]+1;
						}else if (dp[i][j]==tmp) {
							conti[j]=Math.max(conti[j], conti[k]+1);
						}
					}
				}
				System.out.println(i+" "+j+" "+dp[i][j]+" "+conti[j]);
			}
		}
        return dp[0][n-1];
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] boxes={8,6,2,6,6,3,2,3,2,2};
		System.out.println(new RemoveBoxes().removeBoxes(boxes));
	}

}
